package com.squirrel.michale;

import java.util.Arrays;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/2/27 8:04 PM
 * @company Michale Squirrel
 * @link
 * @description
 */
public class LeetCode2517 {

    //Binary Search by Value

    public int maximumTastiness(int[] price, int k) {
        Arrays.sort(price);
        int n = price.length;
        int l = Integer.MAX_VALUE, r = (price[n - 1] - price[0]) / (k - 1);
        for (int i = 1; i < n; i++)
            l = Math.min(l, price[i] - price[i - 1]);

        while (l < r) {
            int mid = ((r - l + 1) >> 1) + l;
            if (k > getCnt(price, mid))
                r = mid - 1;
            else
                l = mid;
        }
        return r;
    }

    private static int getCnt(int[] price, int x) {
        int cnt = 1;
        for (int l = 0, r = 1; r < price.length; r++)
            if (x <= price[r] - price[l]) {
                cnt++;
                l = r;
            }
        return cnt;
    }
}
